package Mydwei;

import java.util.Arrays;

public class DW {
    public int[] elem;
    public int usedsize;

    public DW() {
        this.elem = new int[10];
    }
    public void create(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            elem[i]=arr[i];
            usedsize++;
        }
        for (int p = (usedsize-1-1)/2; p >=0 ; p--) {
            shitfdown(p,usedsize);
        }
    }
    public void shitfdown(int begin,int len){ //向下调正
        int parent=begin;
        int child=2*parent+1;

        while (child<len){
            if(child+1<len&&elem[child]<elem[child+1]){
                child++;
            }
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    public void shiftup(int child){
        int parent=(child-1)/2;
        while (child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }

    public void push(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedsize]=val;
        shiftup(usedsize);
        usedsize++;
    }
    public void pollhead(){
        if(isempty()){
            return;
        }
        int tmp=elem[0];
        elem[0]=elem[usedsize-1];
        elem[usedsize-1]=tmp; //如果是引用类型则需要置为空;
        usedsize--;
        shitfdown(0,usedsize);
    }
    public int peekhead(){
        if(isempty()){
            return -1;
        }
        return elem[0];
    }
    public  void sort(){
        int end =usedsize-1;//这里必须要用end而不能直接用usedsize否则数据就没了，构造函数中的变量都是内部变量，要注意什么时候该删什么时候不该删
        while (end>0){
            int tmp = elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shitfdown(0,end);
            end--;
        }
    }
    public boolean isempty(){
        return usedsize==0;
    }
    public boolean isFull(){
        return usedsize==elem.length;
    }
}
